package simple;

import data.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/6/26 15:48
 */
public class No141_环形链表 {
    public static void main(String[] args) {
        Solution141 solution141 = new Solution141();
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next= new ListNode(-4);
        head.next.next.next.next = head.next;
        boolean b = solution141.hasCycle(head);
        System.out.println(b);
    }
}

class Solution141 {
    public boolean hasCycle(ListNode head) {
        //快慢指针
        if (head == null) {
            return false;
        }

        //定义快慢指针
        ListNode red = head;
        ListNode green = head;
        while (green != null &&
                green.next != null) {
            //先行移动
            red = red.next;
            //走两步
            green = green.next.next;
            //有环,则一定相遇
            if (red == green) {
                return true;
            }
        }
        return false;
    }
}

    //public boolean hasCycle(ListNode head) {
    //    //暴力内存
    //    List<ListNode> list = new ArrayList<>();
    //    while (head != null) {
    //        //查询list
    //        if (list.contains(head)) {
    //            return true;
    //        }
    //        list.add(head);//内存可能撑爆
    //        //指针下移
    //        head = head.next;
    //    }
    //    return false;
    //}